package com.leetcode.problems010;


/**
 * @Description https://leetcode-cn.com/problems/string-to-integer-atoi/
 * @Date 2021/11/20 14:34
 * @Author ghery
 * @Version V1.0
 */
public class Solution {

    private int[][] memo = null;

    public boolean isMatch(String s, String p) {
        if(s.length() == 0 && p.length() == 0){
            return true;
        }
        if(s.length() == 0 || p.length() == 0){
            return false;
        }
        //正则不合法
        if(p.charAt(0) == '*'){
            return false;
        }
        memo = new int[s.length()][p.length()];
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < p.length(); j++) {
                memo[i][j] = -1;
            }
        }
        return match(s,p,0,0);
    }


    private boolean match(String s,String p,int sIndex,int pIndex){

        if(s.length() == sIndex){
            //字符串已遍历完成，检查正则是否完成
            return noMoreMatch(p,pIndex);
        }
        if(p.length() == pIndex){
            //正则遍历完成，字符串还有
            return false;
        }
        if(memo[sIndex][pIndex] != -1){
            return memo[sIndex][pIndex] == 1 ? true : false;
        }
        memo[sIndex][pIndex] = 0;
        //如果正则表达式的下一个字符是 *
        if(pIndex + 1 < p.length() && p.charAt(pIndex + 1) == '*'){
            if(isSample(s.charAt(sIndex),p.charAt(pIndex))){
                if( match(s,p,sIndex + 1,pIndex) || match(s,p,sIndex, pIndex + 2)){
                    memo[sIndex][pIndex] = 1;
                }
            }else{
                if( match(s,p,sIndex,pIndex + 2)){
                    memo[sIndex][pIndex] = 1;
                }
            }
        }else if (isSample(s.charAt(sIndex),p.charAt(pIndex))){
            if( match(s,p,sIndex + 1,pIndex + 1)){
                memo[sIndex][pIndex] = 1;
            }
        }
        return memo[sIndex][pIndex] == 1 ? true : false;
    }

    private boolean noMoreMatch(String p, int pIndex){
        int i = pIndex;
        for(; i < p.length(); i += 2) {
            if (i + 1 < p.length() && p.charAt(i + 1) != '*'){ return false;}
        }
        return i == p.length();
    }

    private boolean isSample(char s,char p) {
        return s == p || p  == '.';
    }

    public static void main(String[] args) {
        System.out.println(new Solution().isMatch("aaa","aa*"));
    }
}
